Rate Limiting Nullifier(RLN)

背景

RLN（Rate limiting nullfier）とは、Ethereumのような分散化された匿名環境におけるスパム防止メカニズム

匿名性はユーザーのプライバシーを守る一方で、以下の攻撃にさらされる

スパム攻撃

シビル攻撃

これにより、UXが損なわれる。例えば以下の例が挙げられる。

投票

スパム防止機構がなければ、投票結果は簡単に操作でき、その結果、アプリケーションは使用できなくなる

完全匿名のグループチャットアプリケーション:

適切なスパム防止機構がないと、誰でも簡単にグループチャットを汚すことができる

メッセージの発信元が不明なので、アプリケーションはスパマーを認識して排除することができない。

アプリケーションがスパマーを適切に除去できたとしても、新しい擬似匿名のアイデンティティが簡単に生成され、アプリケーションを汚染する可能性がある(シビル攻撃)

したがって、匿名性を可能にする信頼性の高いスパム検出および防止メカニズムを持つことは非常に重要になる。

RLN構造とは

RLN構造は、グループメンバーが登録するIDの複製コストを増加させることにより、シビル攻撃を防止する。

アプリケーショに参加するためには、ユーザーにとって価値の高い経済的または社会的なステークを提供しなければならない

ETHやTwitterのアカウントなど

このようなユーザー・アイデンティティの複製は、非常にコストがかかるか、場合によっては不可能

これもアプリケーションによる

ステークを提供してもユーザーのアイデンティティは明らかにならず、アプリケーション利用のための認証情報に過ぎない

ユーザーの認証情報は、ユーザーのステークに関連付けられる

RLNコントラクトの証明システムでは、アンチスパムルールを破った際に、ユーザーの認証情報を明らかにすることが義務付けられており、これを持つことで、誰もがそのユーザーをアプリケーションから排除し、ステークを引き出すことができる。

slashingですな

数学的準備

主に、ふたつの数学的要素がキモになる

ゼロ知識証明(ZKP)

みんな大好きなアレ

シャミアの秘密分散法(SSS)

多項式を用いて秘密を共有する

SSSでは、「秘密を複数の共有に分割し、その中から元の秘密を再構成するために必要な最小数を選ぶ」ことができる

「秘密（M, N）を確実に再構成するためには、N個のうち任意のM個の共有が必要である」とも訳せる

この最小数は、スキームに使われている多項式によって決まる。秘密を復元するのに必要な最小シェア数をXとすると、X-1次の多項式を使う必要がある。

全体の流れ

RLNアプリケーションは中央集権でも分散型でも構築が可能だが、分散型アプリケーションでは、各ユーザーがアプリケーション用に個別のストレージと計算リソースを維持する。そしてこれは、次の3ステップで構築される

1.user registration

2.user interactions

3.user removal

1.user registration

アプリケーションに登録する前に、ユーザは秘密鍵を生成し、Poseidon ハッシュ関数を使用して秘密鍵から ID コミットメントを導出する

code:commitment

identityCommitment = posseidonHash(secretKey))

ユーザは、ステークの形式と、秘密鍵から導かれるアイデンティティ・コミットメントを提供して、アプリケー ションに登録する。アプリケーションは、登録されたユーザの ID コミットメントを保存する Merkle ツリー・データ構造を維持しており、登録に成功すると、ユーザのアイデンティティ・コミットメントはMerkleツリーのリーフに格納され、ツリー内の位置を表すインデックスが与えられる。

2.user interactions

ユーザは、アプリケーションとのインタラクションごとに、ゼロ知識証明を生成する

この証明は、他の参加者（検証者）に対して、「自分がアプリケーションの有効なメンバーであり、自分のアイデンティティ・コミットメントがメンバーシップMerkleツリーの一部である」ことを保証する

スパム対策ルールもプロトコルに導入されていて、次のような形式に一般化される。

ユーザーは、1エポックあたりX回以上のインタラクションを行ってはならない。

エポックは、タイムユニットZのYユニットの時間間隔と訳すことができる。例えばこんな感じ

ユーザーは、1秒間に1通以上のメッセージを送信してはならない。

このスパム対策ルールは、SSSを用いて実装されている。

この例では、秘密=ユーザーの秘密鍵であり、シェア=秘密鍵の一部

簡単なスパム対策ルールとして、以下のルールを考える

線形多項式を用いて(2,3)SSS方式(3個のうち任意の2個の共有が必要であるSSS)を実装する。

つまり、ユーザーが1エポックあたり2つのメッセージを送信すれば、ユーザーの秘密鍵を再構築できる

これが成り立つためには、ユーザーのZKPには、秘密鍵の共有（XとYの共有）とエポックも含まれていなければならない。

これらの項目が含まれていない場合、検証不可能なので,そのZKPは無効なものとして扱われる

ユーザーは、インタラクションを行うたびに、自分の秘密鍵の一部を漏らしていることになる。したがって、エポックごとに許可されている以上のインタラクションを行うと、検証者によって秘密鍵が完全に再構築されてしまう。

スパム耐性はありそう。あれ？シビル耐性はどこ？

→登録時のステークの重みか

3.user removal

秘密鍵を知っている誰もが、メンバーシップ・ツリーからユーザを削除できる。

メンバーシップ・ツリーには、登録されたすべてのユーザのアイデンティティ・コミットメントが含まれており、これは彼らの秘密鍵から導かれ、ユーザーの秘密鍵はアンチスパムルールを破った際にのみ明らかにされる。

経済的なステークが存在する場合、RLNメカニズムはスパマーのステークが、証明としてスパマーの再構築された秘密鍵を提供することによりスパマーを正しく報告した最初のユーザーに送られるという方法で実装することができる。

RLN構造を利用したアプリの流れ

https://scrapbox.io/files/617fbf423cfc690022a38017.png

ステップ1：Charlieはアクティブな参加者になりたいと考え、スマートコントラクトに登録トランザクションを送信し、彼のステークを提供する。スマートコントラクトは新しいIDコミットメントが登録されたというイベントを発行し、各ユーザーは新しく登録されたIDコミットメントでRLNメンバーシップツリーを更新する必要があります。

https://scrapbox.io/files/617fbf4900d81a001dde9826.png

ステップ2： Charlieは、エポック1で、必要なパラメータと有効なZK証明をすべて含んだメッセージをAliceとBobに送信します。

https://scrapbox.io/files/617fbf53b5c018001df5baec.png

Step3：Charlieは、エポック1の2番目のメッセージをAliceとBobに送信します。メッセージのパラメータはすべて有効であり、ZK証明も有効であるしかし、Charlieはスパム対策ルールに違反しており、AliceとBobはCharlieの秘密鍵を再構築し、RLNメンバーシップツリーから彼を削除することができる。

https://scrapbox.io/files/617fbf64d1a32e001dc6614e.png

ステップ4：AliceはRLN Membershipスマートコントラクトに出金トランザクションを送信し、Charlieのステークを引き出しますスマートコントラクトは、Charlieがアプリケーションから禁止されており、すべてのユーザーがそのようにフラグを立てるべきであることを知らせるイベントを発します。

Merkle Tree

メンバーシップのZKPは、グループ全体をMerkle Treeとして表現しており、木の構築と維持はピアに委ねられている。そのため、各ピアはローカル環境にツリーを構築し、コントラクトの更新（ピアの挿入と削除）を自身のツリーに反映させるために同期を取る必要がある。

ピアがZKPを生成するために2つの情報(ツリーのルートとメンバーシップ証明（または認証パス）)がツリーに格納される。

ツリーのルートは公開情報であるのに対し、メンバーシップ証明はプライベートデータ（正確には、ツリー内のピアのインデックス）

ZKP

任意のエポックで公開するためには、各メッセージに、公開するユーザーが登録メンバーであり、任意のエポックでメッセージング・レートを超えていないことを示す証明（ゼロ知識証明）を添付する必要がある。

メッセージング・レートの実施は、メッセージに相手のskの秘密共有バージョンを関連付け、秘密共有が正しく構築されていることを示すZKPを行うことで行われました。秘密共有の部分については、ピアは以下のデータを生成します。

shareX

shareY

Nullifier

このペア（shareX, shareY）は、SSSで生成されたskの秘密分散版。同一のNullifierに対してこのようなペアが2つあると、ピアのskが完全に開示されることになり、その結果、関連するステークがburnすることになる。Nullifierはskとエポックから得られる決定論的な値であるため、同じエポックで同じピアが発行した（つまり同じskを使用した）2つのメッセージは、同一のNullifierを持つことが保証される

最後に、ピアは、グループ内のピアのメンバーシップと、添付された秘密共有（shareX、shareY）およびNullifierの正しさを主張するZKPを生成する。有効な証明を生成するためには、ピアは2つのプライベート入力、すなわち、そのskとその認証パスを持つ必要があります。その他の入力は、ツリーのルート、エポック、メッセージの内容である。

プライバシーに関するヒント：各ピアの認証パスは、最近のメンバーリストに依存していることに注意してください（したがって、新しいピアが登録または退出すると変更されます）。そのため、パブリッシャーはグループの最新の状態に基づいて認証パスを更新し、更新されたバージョンを使用して証明を試みることが推奨されます (プライバシー/匿名性のためにも必要です)。

Signal; What you are saying

External_nullfiers; This prevents the linking of differnt signals together.

nullifiers; hash(extrenal_nullfier , leaf_private_key) which is a finger print uniuq to this member for this external_nullifier.

External_nullfiers=エポック

ルーティング

ルーティング・ピアは、メッセージを受信すると、そのメッセージをルーティングするかどうかを決定する必要がある。

この決定は以下の要素に依存する。

1) メッセージに添付されたエポック値が、ルーティングピアの現在のエポックと合理的でないギャップがある場合、メッセージはドロップされなければならない

これは、新規に登録されたピアが、過去のすべてのエポックのメッセージを送信してシステムをスパムすることを防ぐため

2) メッセージは、ルーティングピアによって検証される有効な証明を含まなければならない。

前述のチェックが正常に通過した場合、メッセージは中継される。

無効な証明の場合、メッセージはドロップされる。

スパム行為が検出された場合、パブリッシングピアはslashされる

slashing

ローカルでのスパム検出とスラッシングを可能にするために、ルーティングピアは、スパムではなく、有効な証明があることを条件に、受信メッセージのnullifier、shareX、shareYを記録しなければならない。これを行うために、ピアは以下の手順を踏む

1.ルーティングピアはまずzkProofを検証し、検証されていない場合はメッセージをドロップする。

2.そうでなければ、同一のヌルファイアを持つメッセージがすでにリレーされているかどうかをチェック

a) そのようなメッセージが存在し、そのshareXとshareYの構成要素が着信メッセージと異なる場合、スラッシングが行われる（以前に中継されたメッセージのshareXとshareYのフィールドが着信メッセージと同一である場合、そのメッセージは重複であり、ドロップされなければならない）。

b) 見つからなければ、メッセージを中継する。